﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0069_MinSubArrayLen : IAlgorithm
    {
        // 209. 长度最小的子数组

        // 给定一个含有 n 个正整数的数组和一个正整数 target 。

        // 找出该数组中满足其和 ≥ target 的长度最小的 连续子数组[numsl, numsl + 1, ..., numsr - 1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

        // 提示：
        //  1 <= target <= 10^9
        //  1 <= nums.length <= 10^5
        //  1 <= nums[i] <= 10^5

        // 进阶：
        //  如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。

        public void Test()
        {
            // 算法参数定义
            int target = 11;
            int[] nums = new int[] { 1, 2, 3, 4, 5 };
            // 算法执行与打印
            Console.WriteLine(MinSubArrayLen(target, nums));
        }

        // 算法
        public int MinSubArrayLen(int target, int[] nums)
        {
            if (nums.Length == 0)
                return 0;
            int l = 0, r = 0;
            int sum = 0;
            int minLen = 0;
            while (r < nums.Length)
            {
                sum += nums[r];
                while (sum >= target)
                {
                    if (minLen == 0)
                        minLen = r - l + 1;
                    else
                        minLen = Math.Min(minLen, r - l + 1);
                    sum -= nums[l++];
                }
                r++;
            }
            return minLen;
        }

        private int LowerBound(int[] a, int l, int r, int target)
        {
            int mid = -1, originL = l, originR = r;
            while (l < r)
            {
                mid = (l + r) >> 1;
                if (a[mid] < target) l = mid + 1;
                else r = mid;
            }

            return (a[l] >= target) ? l : -1;
        }
        public int MinSubArrayLen1(int s, int[] nums)
        {
            int n = nums.Length;
            if (n == 0)
            {
                return 0;
            }

            int ans = int.MaxValue;
            int[] sums = new int[n + 1];
            // 为了方便计算，令 size = n + 1 
            // sums[0] = 0 意味着前 0 个元素的前缀和为 0
            // sums[1] = A[0] 前 1 个元素的前缀和为 A[0]
            // 以此类推
            for (int i = 1; i <= n; ++i)
            {
                sums[i] = sums[i - 1] + nums[i - 1];
            }

            for (int i = 1; i <= n; ++i)
            {
                int target = s + sums[i - 1];
                int bound = LowerBound(sums, i, n, target);
                if (bound != -1)
                {
                    ans = Math.Min(ans, bound - i + 1);
                }
            }

            return ans == int.MaxValue ? 0 : ans;
        }
    }
}
